成为架构师系列一：如何设计一个高效的速率限制器来保护你的系统
这个系列很难，但是它是程序员走向架构师所必备的知识，既能助你在面试中脱颖而出，也能让你在日常工作中游刃有余。从基础到深入，从理论到实践，一切你所需的都在这里。收藏本文，点击关注
在网络系统中，速率限制器被用来控制客户端或服务发送的流量的速率。在 HTTP 领域，速率限制器限制了在指定周期内允许发送的客户端请求的数量。如果 API 请求的数量超过了速率限制器定义的阈值，所有超出的调用都会被阻止。以下是一些示例：
• 用户每秒钟最多只能发布2篇帖子。
• 你可以每天最多从同一 IP 地址创建10个帐户。
• 你可以每周最多从同一设备领取5次奖励。
在这一章中，我们一起来设计一个速率限制器。在开始设计之前，我们首先看一下使用 API 速率限制器的好处：
• 防止由DoS攻击[1]引起的资源耗尽。几乎所有大型科技公司发布的 API 都执行一些形式的速率限制。例如，Twitter 限制每3小时的推文数量为300条。Google 文档的 API 默认限制为：对于读取请求，每个用户每60秒300个。速率限制器通过阻止过量的调用来防止 DoS 攻击，无论是有意还是无意的。
• 减少成本。限制过量的请求意味着更少的服务器和将更多的资源分配给高优先级的 API。对于使用付费第三方 API 的公司来说，速率限制极其重要。例如，你按次收费的外部 API 包括：查看信用，进行支付，获取健康记录等。限制调用次数是减少成本的关键。
• 防止服务器过载。为了减少服务器负载，速率限制器被用来过滤由机器人或用户的不当行为引起的过量请求。
第一步 - 理解问题并确定设计范围
速率限制可以通过不同的算法来实现，每种算法都有其优点和缺点。和面试官的交流有助于理解面试官要求构建的速率限制器的类型。
面试者：我们要设计的是哪种类型的速率限制器？是客户端速率限制器还是服务器端 API 速率限制器？
面试官：好问题。我们关注的是服务器端的 API 速率限制器。
面试者：速率限制器是基于 IP、用户 ID 还是其他属性来对 API 请求进行限流的？
面试官：速率限制器应该足够灵活，能支持不同的限流规则。
面试者：系统的规模如何？是为初创公司构建的，还是为拥有大量用户基础的大公司构建的？
面试官：系统必须能处理大量的请求。
面试者：系统会在分布式环境下工作吗？
面试官：是的。
面试者：速率限制器是一个单独的服务，还是应该在应用程序代码中实现？
面试官：这是由你来决定的设计决策。
面试者：我们需要通知被限流的用户吗？
面试官：是的。
需求
以下是系统的需求摘要：
• 准确地限制过量的请求。
• 低延迟。速率限制器不应降低 HTTP 响应时间。
• 尽可能少地使用内存。
• 分布式速率限制。速率限制器可以在多个服务器或进程之间共享。
• 异常处理。当用户的请求被限流时，向用户显示清晰的异常。
• 高容错性。如果速率限制器出现任何问题（例如，缓存服务器宕机），它不会影响整个系统。
第二步 - 提出高层次设计并获得认可
让我们从简单的设计入手，使用基本的客户端和服务器模型进行通信。
应该在哪里放置速率限制器？
一般来说，你可以在客户端或服务器端实现速率限制器。
• 客户端实现。一般来说，客户端是实施速率限制的不可靠地方，因为恶意参与者可以轻易地伪造客户端请求。此外，我们可能无法控制客户端的实现。
• 服务器端实现。图 4-1 显示了放置在服务器端的速率限制器。
除了客户端和服务器端的实现，还有另一种方式。我们不是在 API 服务器上放置速率限制器，而是创建一个速率限制中间件，如图 4-2 所示，对你的 API 的请求进行限流。
让我们用图 4-3 中的一个例子来说明这种设计中的速率限制是如何工作的。
假设我们的 API 每秒允许 2 个请求，客户端在一秒钟内向服务器发送 3 个请求。前两个请求被路由到 API 服务器。然而，速率限制中间件限流第三个请求并返回 HTTP 状态码 429。HTTP 429 响应状态码表示用户发送的请求过多。
如果你的系统部署在云服务上，速率限制通常是在API 网关的组件内实现的。API 网关是一个全面管理的服务，支持速率限制、SSL 认证、身份验证、IP 白名单、服务静态内容等。目前，我们只需要知道 API 网关是一个支持速率限制的中间件。
在设计速率限制器时，我们考虑一个重要的问题：速率限制器应该在服务器端实现还是在网关中实现？这个问题没有绝对的答案。它取决于你公司现有的技术栈、工程资源、优先事项、目标等。以下是一些一般性的指南：
• 评估你当前的技术栈，如编程语言、缓存服务等。确保你当前的编程语言足够高效，能在服务器端实现速率限制。
• 确定符合你业务需求的速率限制算法。当你在服务器端实现所有功能时，你可以完全控制算法。如果你使用第三方网关，你的选择可能不会太多。
• 如果你已经使用了微服务架构，并在设计中包含了 API 网关来进行身份验证、IP 白名单等操作，你可以在 API 网关中添加速率限制器。
• 自己开发速率限制服务需要时间。如果你没有足够的工程资源来实现速率限制器，云厂商的 API 网关是一个更好的选择。
速率限制的算法
我们可以使用不同的算法实现速率限制，每种算法都有其独特的优点和缺点。虽然本文不专注于算法，但是高层次的理解有助于我们选择适合我们业务的正确算法或算法组合。下面是一些常见的算法：
• 令牌桶
• 漏桶
• 固定窗口计数器
• 滑动窗口日志
• 滑动窗口计数器
令牌桶算法
令牌桶算法是一种很流行的速率限制算法。它简单、易于理解，并且被互联网公司广泛使用。亚马逊和 Stripe都使用这种算法来限制他们的 API 请求。
令牌桶算法的工作原理如下：
• 令牌桶是一个具有预定义容量的容器。令牌按预设的速率定期放入桶中。一旦桶满，就不再添加令牌。如图4-4所示，令牌桶的容量是4。每秒填充器向桶中放入2个令牌。一旦桶满，额外的令牌将溢出。
• 每个请求消耗一个令牌。当请求到达时，我们检查桶中是否有足够的令牌。图4-5解释了它是如何工作的。
• 如果有足够的令牌，我们为每个请求取出一个令牌，请求通过。
• 如果没有足够的令牌，请求将被丢弃。
图4-6说明了令牌消耗、填充和速率限制逻辑是如何工作的。在这个例子中，令牌桶的大小是4，填充速率是每1分钟4个。
令牌桶算法有两个参数：
• 桶大小：桶中允许的最大令牌数量
• 填充速率：每秒钟放入桶中的令牌数量
我们需要多少个桶呢？这是不固定的，取决于限速规则。以下是一些例子。
• 对于不同的API端点，通常需要有不同的桶。例如，如果用户每秒允许发表1篇帖子，每天添加150个好友，每秒点赞5篇帖子，每个用户需要3个桶。
• 如果我们需要基于IP地址限制请求，那么每个IP地址需要一个桶。
• 如果系统每秒钟允许最多10,000个请求，那么让所有请求共享一个全局桶则是一个最优解。
优点：
• 算法易于实现。
• 内存效率高。
• 令牌桶允许在短时间内进行流量爆发。只要还有剩余的令牌，请求就可以通过。
缺点：
• 算法中的两个参数是桶的大小和令牌填充速率。然而，正确地调整它们可能会很具挑战性。
漏桶算法
漏桶算法与令牌桶算法类似，只是以固定速率处理请求。它通常使用先进先出（FIFO）的队列实现。该算法的工作原理如下：
• 当请求到达时，系统检查队列是否已满。如果没有满，请求被添加到队列中。
• 如果队列已满，请求将被丢弃。
• 请求在规定的时间间隔内从队列中取出并处理。
图4-7解释了算法的工作原理。
漏桶算法需要以下两个参数：
• 桶（队列）大小：队列按固定速率保存待处理的请求。
• 出流速率：它定义了可以按固定速率处理的请求的数量，通常以秒为单位。
电子商务公司Shopify就是使用漏桶算法进行限速的。
优点：
• 鉴于队列大小有限，内存效率高。
• 请求按固定速率处理，因此适用于需要稳定出流速率的情况。
缺点：
• 流量爆发将使队列充满旧的请求，如果它们没有及时处理，则新的请求将受到速率限制。
• 这个算法中的两个参数不是很容易找到最优解。
固定窗口计数器算法
固定窗口计数器算法的工作原理如下：
• 该算法将时间线划分为固定大小的时间窗口，并为每个窗口分配一个计数器。
• 每个请求将计数器增加一。
• 一旦计数器达到预定义的阈值，新的请求将被丢弃，直到开始新的时间窗口。
让我们用一个具体的例子来看看它是如何工作的。在图4-8中，时间单位是1秒，系统每秒最多允许3个请求。在每个一秒的窗口中，如果接收到超过3个请求，额外的请求将被丢弃，如图4-8所示。
这种算法的一个主要问题是在时间窗口的边缘出现的流量突增可能会导致通过的请求超过允许的配额。比如以下情况：
在图4-9中，系统每分钟最多允许5个请求，可用请求在整分钟时刻重置。如图所示，2:00:00至2:01:00之间有五个请求，2:01:00至2:02:00之间又有五个请求。对于2:00:30至2:01:30的一分钟窗口，通过了10个请求。这是允许请求的两倍。
优点：
• 内存效率高。
• 易于理解。
• 在时间窗口结束时重置可用配额适合某些用例。
缺点：
• 在窗口边缘的流量突增可能会导致通过的请求超过允许的配额。
滑动窗口日志算法
正如我们之前讨论过的，固定窗口计数器算法有一个主要问题：它在窗口的边缘允许通过更多的请求。滑动窗口日志算法解决了这个问题。它的工作原理如下：
• 该算法记录请求的时间戳。时间戳数据通常保存在缓存中，例如Redis的有序集合。
• 当一个新的请求进来时，删除所有过时的时间戳。过时的时间戳的定义是：比当前时间窗口开始时间更早的时间戳。
• 将新请求的时间戳添加到日志中。
• 如果日志大小等于或小于允许的数量，请求被接受。否则，它会被拒绝。
我们用一个例子来解释这个算法，如图4-10所示。
在这个例子中，速率限制器每分钟允许2个请求。通常，在日志中存储的是Linux时间戳。但是，为了更好的可读性，我在例子中使用了人类可读的时间表示法。
• 当新的请求在1:00:01到达时，日志是空的。因此，该请求被允许。
• 新的请求在1:00:30到达，时间戳1:00:30被插入到日志中。插入后，日志的大小为2，没有超过允许的计数。因此，该请求被允许。
• 新的请求在1:00:50到达，时间戳也被插入到日志中。插入后，日志的大小为3，超过了允许的大小2。因此，即使时间戳仍然在日志中，这个请求也被拒绝。
• 新的请求在1:01:40到达。在范围[1:00:40,1:01:40)内的请求都在最新的时间范围内，但在1:00:40之前发送的请求都过时了。两个过时的时间戳，1:00:01和1:00:30，从日志中移除。移除操作后，日志的大小变为2；因此，请求被接受。
优点：
• 这种算法实现的速率限制非常精确。在任何滚动窗口中，请求都不会超过速率限制。
缺点：
• 该算法消耗大量内存，因为即使请求被拒绝，它的时间戳可能仍然存储在内存中。
滑动窗口计数器算法
滑动窗口计数器算法是一种混合方法，结合了固定窗口计数器和滑动窗口日志。这个算法可以通过两种不同的方法实现。我们将在本文解释其中一种实现，并在本专栏后续提供另一种实现的参考。图4-11说明了这种算法是如何工作的。
假设速率限制器每分钟允许最多7个请求，前一分钟有5个请求，当前分钟有3个请求。对于在当前分钟30%位置到达的新请求，滚动窗口内的请求数量是用以下公式计算的：
• 当前窗口中的请求 + 上一个窗口中的请求 ***** 滚动窗口和上一个窗口的重叠百分比
• 使用这个公式，我们得到3 + 5 * 0.7% = 6.5个请求。根据使用场景，这个数字可以四舍五入。在我们的例子中，它被舍入为6。
由于速率限制器每分钟允许最多7个请求，当前的请求可以通过。然而，再收到一个请求后，限制将被达到。
由于篇幅限制，我们不会在这里讨论另一种实现。感兴趣的读者可以关注下我，后续我会解释。这个算法并不完美，它有优点和缺点。
优点：
• 它能够平滑流量峰值（削峰），因为速率基于前一个窗口的平均速率。
• 内存效率高。
缺点：
• 它只适用于不那么严格的回溯窗口。它只是近似于实际速率，因为它的前提是假设在前一个窗口中的请求是均匀分布的。但是实际情况，这个算法并不像理论上那么差。根据Cloudflare的实验，4亿请求中只有0.003%的请求被错误地放行或限速了。
高级架构
速率限制算法的基本思想很简单。在更高的层面，我们需要一个计数器来跟踪同一用户、IP地址等发送的请求数量。如果计数器的数值大于限制，那么请求就会被拒绝。
那我们应该在哪里存储计数器呢？由于磁盘访问速度慢，使用数据库也不是一个好主意。因此一般推荐内存缓存，因为它快速并支持基于时间的过期策略。Redis是实现速率限制的一个主流选项。它是一个内存存储，提供了两个命令：INCR和EXPIRE。
• INCR：它将存储的计数器增加1。
• EXPIRE：它为计数器设置一个超时时间。如果超时到期，计数器会自动删除。
图4-12显示了速率限制的高级架构，其工作流程如下：
• 客户端向速率限制中间件发送请求。
• 速率限制中间件从Redis中相应的存储桶获取计数器，并检查限制是否已经达到。
• 如果达到了限制，请求将被拒绝。
• 如果没有达到限制，请求将被发送到API服务器。同时，系统会增加计数器并将其保存回Redis。
第三步 - 深入设计
图4-12中的高级设计并没有回答以下问题：
• 速率限制规则是如何创建的？规则存储在哪里？
• 如何处理被限速的请求？
在本节中，我们将首先回答关于速率限制规则的问题，然后讨论处理被限速请求的策略。最后，我们将讨论分布式环境中的速率限制、详细设计、性能优化和监控。
速率限制规则
Lyft开源了他们的速率限制组件。我们来深入这个组件并查看一些速率限制规则的例子：
domain: messaging descriptors:
• key: message_type value: marketing rate_limit: unit: day requests_per_unit: 5
在上面的例子中，系统配置为每天允许最多5条营销信息。
domain: auth descriptors:
• key: auth_type value: login rate_limit: unit: minute requests_per_unit: 5
这条规则表明客户端在1分钟内不允许登录超过5次。规则通常写在配置文件中并保存在磁盘上。
超过速率限制
如果一个请求受到了速率限制，APIs会向客户端返回HTTP响应码429（请求过多）。根据使用场景，我们可能会将受到速率限制的请求加入队列以便稍后处理。例如，如果一些订单由于系统过载而受到速率限制，我们可能会保留这些订单以便稍后处理。
速率限制器头（header）
客户端如何知道它是否正在被限流？客户端如何知道在被限流之前允许的剩余请求数量？答案在HTTP响应头中。速率限制器向客户端返回以下HTTP头：
X-Ratelimit-Remaining：在窗口内允许的剩余请求数量。
X-Ratelimit-Limit：指示客户端每个时间窗口可以进行多少次调用。
X-Ratelimit-Retry-After：在不被限流的情况下，等待多少秒后可以再次发送请求。
当用户发送的请求过多时，我们应该向客户端返回429过多请求错误和X-Ratelimit-Retry-After header。
详细设计
图4-13展示了系统的详细设计。
• 规则存储在磁盘上。有一个单独的进程定期从磁盘中提取规则并将它们存储在缓存中。
• 当客户端向服务器发送请求时，请求首先发送到速率限制中间件。
• 速率限制中间件从缓存中加载规则。它从Redis缓存中获取计数器和上一个请求的时间戳。根据响应，速率限制器决定：
• 如果请求没有被限速，它会被转发到API服务器。
• 如果请求被限速，速率限制器返回429过多的请求错误给客户端。同时，请求被丢弃或转发到队列中。
分布式环境中的速率限制器
在单服务器环境中构建一个速率限制器并不困难。然而，将系统扩展以支持多个服务器和并发线程是另一个挑战。有两个挑战：
• 竞态条件
• 同步问题
竞态条件
如前所述，速率限制器在高级别上按照以下方式工作：
• 从Redis读取计数器的值。
• 检查(计数器 + 1)是否超过阈值。
• 如果没有，就在Redis中将计数器的值增加1。
在高并发的环境中，可能会发生竞态条件，如图4-14所示。
假设Redis中的计数器值为3。如果在请求写回之前，两个请求同时读取计数器值，每个请求都会将计数器增加1，然后在不检查其他线程的情况下写回。两个请求（线程）都认为他们拥有正确的计数器值4。然而，正确的计数器值应该是5。
锁是解决竞态条件的最简单的解决方案。然而，锁会显著降低系统的速度。这里通常用两种策略来解决这个问题：Lua脚本和Redis中的有序集数据结构。对这些策略感兴趣的读者，可以关注我，之后我会专门开一篇讲这个。
同步问题
在分布式环境中，同步是另一个需要考虑的重要因素。为了支持数百万用户，一个速率限制器服务器是无法处理所有的流量的。当使用多个速率限制器服务器时，需要进行同步。例如，在图4-15的左侧，客户端1向速率限制器1发送请求，客户端2向速率限制器2发送请求。
由于Web层是无状态的，客户端可以向不同的速率限制器发送请求，如图4-15的右侧所示。如果没有发生同步，速率限制器1就不包含关于客户端2的任何数据。因此，速率限制器无法正常工作。
一个可能的解决方案是使用粘性会话（stick session），让客户端将流量发送到同一速率限制器。这个解决方案是不建议使用的，因为它既不可扩展也不灵活。更好的方法是使用像Redis这样的集中式数据存储。设计如图4-16所示。
性能优化
性能优化是系统设计面试中的常见话题。关于今天的主题我们将探讨两个需要改进的点。
首先，多数据中心的设置对于速率限制器非常关键，因为对于远离数据中心的用户来说，延迟很高。大多数云服务提供商在全球各地建立许多边缘服务器位置。截至2020年5月20日，Cloudflare在地理上分布有194个边缘服务器[14]。流量会自动路由到最近的边缘服务器，以减少延迟。
其次，用最终一致性模型同步数据。如果你对最终一致性模型不清楚，也请关注我，我后续会开一篇单独来讲这个。
监控
在放置速率限制器后，收集分析数据以检查速率限制器是否有效是非常重要的。我们想要确保：
• 速率限制算法是有效的。
• 速率限制规则是有效的。
例如，如果速率限制规则过于严格，许多有效的请求将被丢弃。在这种情况下，我们可能希望稍微放宽规则。或者我们注意到当流量突然增加，如秒杀活动开始时，我们的速率限制器就会不符合场景。在这种情况下，我们可以更换算法以支持突发流量。在这个场景下令牌桶是一个很好的选择。
步骤四 - 总结
在这一章中，我们讨论了不同的速率限制算法及其优点/缺点。我们讨论的算法包括：
• 令牌桶
• 漏桶
• 固定窗口
• 滑动窗口日志
• 滑动窗口计数器
然后，我们讨论了系统架构，分布式环境中的速率限制器，性能优化和监控。类似于任何系统设计面试问题，如果时间允许，我们还可以提到其他的讨论点：
• 硬速率限制 vs 软速率限制。
• 硬限制：请求次数不能超过阈值。
• 软限制：请求在短时间内可以超过阈值。
• 在不同层级的速率限制。在本文中，我们只讨论了应用层级（HTTP：第7层）的速率限制。在其他层也可以应用速率限制。例如，你可以使用Iptables（IP：第3层）通过IP地址进行速率限制。给大家补下课：OSI模型（开放系统互联模型）有7层：第1层：物理层，第2层：数据链路层，第3层：网络层，第4层：传输层，第5层：会话层，第6层：表示层，第7层：应用层。
• 如何改进客户端：
• 使用客户端缓存以避免频繁地调用API。
• 理解限制，并且不在短时间内发送过多的请求。
• 包含捕获异常或错误的代码，以便你的客户端可以从异常中优雅地恢复。
• 在重试逻辑中添加足够的退避时间。
祝贺你走到这一步！现在给自己一个赞。做得好！
参考资料
[1] 速率限制策略和技术：https://cloud.google.com/solutions/rate-limiting-strategies-techniques
[2] Twitter速率限制：https://developer.twitter.com/en/docs/basics/rate-limits
[3] Google文档使用限制：https://developers.google.com/docs/api/limits
[4] IBM微服务：https://www.ibm.com/cloud/learn/microservices
[5] 节流API请求以获得更好的吞吐量：
https://docs.aws.amazon.com/apigateway/latest/developerguide/api-gateway-request-throttling.html
[6] Stripe速率限制器：https://stripe.com/blog/rate-limiters
[7] Shopify REST Admin API速率限制：https://help.shopify.com/en/api/reference/rest-admin-api-rate-limits
[8] 使用Redis排序集合实现更好的速率限制：https://engineering.classdojo.com/blog/2015/02/06/rolling-rate-limiter/
[9] 系统设计 — 速率限制器和数据建模：https://medium.com/@saisandeepmopuri/system-design-rate-limiter-and-data-modelling- 9304b0d18250
[10] 我们如何建立能扩展到数百万域名的速率限制器：https://blog.cloudflare.com/counting-things-a-lot-of-different-things/
[11] Redis网站：https://redis.io/
[12] Lyft速率限制：https://github.com/lyft/ratelimit
[13] 使用速率限制器扩展你的API：https://gist.github.com/ptarjan/e38f45f2dfe601419ca3af937fff574d#request-rate-limiter
[14] 什么是边缘计算：https://www.cloudflare.com/learning/serverless/glossary/what- is-edge-computing/
[15] 使用Iptables限制请求速率：https://blog.programster.org/rate-limit-requests-with- iptables
[16] OSI模型：https://en.wikipedia.org/wiki/OSI_model#Layer_architecture
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。